package com.tgy.algorithm.base;


import java.util.EmptyStackException;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 使用两个队列实现栈的功能
    1 2 3 4

 */
class MyStack{
    private Queue<Integer> firstQueue;
    private Queue<Integer> secondQueue;

    MyStack(){
       this.firstQueue = new LinkedList<Integer>();
       this.secondQueue = new LinkedList<Integer>();
    }

    // 进栈
    public void push(int x){
        firstQueue.offer(x);
    }

    public int pop(){

        if(this.isEmpty()){
            throw new EmptyStackException();
        }

        int rest = 0;
        while(!firstQueue.isEmpty() && firstQueue.size() > 1){
            secondQueue.offer(firstQueue.poll());
        }

        rest = firstQueue.poll();
        // 让第一个队列与第二个队列进行进行交互
        Queue<Integer> tmpQueue = firstQueue;
        firstQueue = secondQueue;
        secondQueue = tmpQueue;
        return rest;
    }

    public boolean isEmpty(){
        return firstQueue.isEmpty();
    }
}

public class _队列实现栈 {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        // 1 2 4
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        int val = myStack.pop();
        System.out.println(val);
        myStack.push(4);
        myStack.push(5);
        System.out.println(myStack.pop());

        while (!myStack.isEmpty()){
            System.out.println(myStack.pop());
        }
    }
}
